1. Field of the Invention
The present invention relates generally to set mapping, and, more particularly, to a low cost and low complexity method and apparatus for efficiently mapping one set containing N elements into another set containing N elements.
2. Related Art
Computer graphics systems commonly are used for displaying graphical representations of objects on a two-dimensional computer display screen. Current computer graphics systems can provide highly detailed representations and are used in a variety of applications.
In some computer graphics systems, and in other systems such as communication systems, set mapping functionality is necessary in the course of system design. The set mapping function is typically accessed repeatedly as system constraints change over time. A typical set mapping function calls for each of the N members of a set (set A) to be associated with one and only one of the N members of another set (set B). For example, where N broadcasters are mapped into N available channels. Each of these associations is a possible set mapping solution.
The set mapping function is typically cost optimized in that each mapping solution has a particular cost associated therewith. This cost is typically assigned by a device located within the system that continuously monitors data availability in memory and data requests in a memory controller. As the set size increases (for example, mapping a set containing eight (8) elements into another set containing eight (8) elements), the computation resources required to generate the optimal mapping solution become excessive. To illustrate for the mapping function mentioned above, there are N! possible legal mapping possibilities. Assuming that N=2.sup.m, where m is an integer, (N-1)*N adders and (N!-1) comparators are required to calculate the optimal mapping solution. For N=8, this implies that 280000 adders and 40000 comparators are required to map a set containing eight elements into a set containing eight elements.
Thus, an unaddressed need exists in the industry for a more efficient method and apparatus for generating a cost optimized mapping solution for mapping sets containing N elements into sets containing N elements.